package com.code.test.dance;


/**
 * 给你一个链表数组，每个链表都已经按升序排列。
 * <p>
 * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
 *
 * https://juejin.cn/post/6844904198555992077
 */
public class MergeKList {
    public static void main(String[] args) {
        LinkNode head = new LinkNode(1);
        LinkNode second = new LinkNode(2);
        LinkNode third = new LinkNode(3);
        LinkNode n4 = new LinkNode(4);
        LinkNode n5 = new LinkNode(5);
        LinkNode n6 = new LinkNode(6);
        LinkNode n7 = new LinkNode(7);

        head.setNext(second);
        second.setNext(third);
        third.setNext(n4);
        n4.setNext(n5);
        n5.setNext(n6);
        n6.setNext(n7);

        LinkNode headB = new LinkNode(3);
        LinkNode secondB = new LinkNode(5);
        LinkNode thirdB = new LinkNode(8);
        headB.next = secondB;
        secondB.next = thirdB;

        LinkNode headC = new LinkNode(4);
        LinkNode secondC = new LinkNode(7);
        LinkNode thirdC = new LinkNode(10);
        headC.next = secondC;
        secondC.next = thirdC;


        LinkNode[] input = {head, headB, headC};
        LinkNode node = mergeKLists2(input);

        int a = 2;

    }

    public static LinkNode mergeKLists2(LinkNode[] lists) {
        if(null == lists || lists.length == 0) {
            return null;
        }
        //
        LinkNode result = lists[0];
        // 从第二个开始遍历
        for(int i = 1; i < lists.length; i++) {
            LinkNode node = lists[i];
            result = mergeTwoLists(result, node);
        }
        return result;
    }

    public static LinkNode mergeTwoLists(LinkNode l1, LinkNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        // 临时变量
        LinkNode newNode = new LinkNode(0);
        // 新增的头指针
        LinkNode head = newNode;
        // 循环处理
        while (l1 != null && l2 != null) {
            int valOne = l1.val;
            int valTwo = l2.val;
            // 插入小的元素节点
            if (valOne <= valTwo) {
                newNode.next = l1;
                l1 = l1.next;
            } else {
                newNode.next = l2;
                l2 = l2.next;
            }
            // 变换 newNode
            newNode = newNode.next;
        }
        // 如果长度不一样
        if (l1 != null) {
            newNode.next = l1;
        }
        if (l2 != null) {
            newNode.next = l2;
        }

        return head.next;
    }
}

